fun main() {
    val n = listOf<Int>(-1, 0, 3, 5, 9, 12)
    test(n, ::search, 9)
    test(n, ::search, 10)
    test(n, ::searchByRecursion, 9)
    test(n, ::searchByRecursion, 10)
}

fun <E: Comparable<E>>test(arr: List<E>, f: (List<E>, E) -> Int, target:E) {
    val result = f(arr, target)
    if (result != -1) {
        println("${arr}中第${result}位 = $target")
    }else {
        println("${arr}中没有 $target")
    }
}

fun <E: Comparable<E>>search(arr: List<E>, target: E): Int {
    var left = 0
    var right = arr.count() -1
    while (left <= right) {
        val mid = left + (right - left) / 2
        if (arr[mid] == target) {
            return mid
        }else if (arr[mid] < target) {
            left = mid + 1
        }else if (arr[mid] > target) {
            right = mid - 1
        }
    }

    return -1
}

fun <E: Comparable<E>>searchByRecursion(arr: List<E>, target: E): Int {
    return recursion(arr, target, 0, arr.size - 1)
}

fun <E: Comparable<E>>recursion(arr: List<E>, target: E, left: Int, right: Int): Int {
    if (left > right) {
        return -1
    }

    val mid = left + (right - left) / 2
    return if (arr[mid] == target) {
        mid
    }else if (arr[mid] < target) {
        recursion(arr, target, mid + 1, right)
    }else {
        recursion(arr, target, left, mid - 1)
    }
}
